class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }
  append(index, element) {
    if (arguments.length == 1) {
      element = index;
      index = this.size;
    }
    if (index > this.size || index < 0) {
      throw new Error("Index out of bounds");
    }
    // 插入头部
    if (index === 0) {
      // 暂存一下当前的头部
      let head = this.head;
      // 重新赋值头部数据，并把暂存的头部数据作为新头数据的next
      this.head = new Node(element, head);
    } else {
      // 暂存一下插入节点前一个数据node
      let preNode = this.getNode(index - 1);
      // 设置暂存的前一个数据的next节点为新的node节点
      preNode.next = new Node(element, preNode.next);
    }
    this.size++;
  }
  getNode(index) {
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }
    return current;
  }
  reverseList() {
    // 使用递归对换位置
    const reverse = (head) => {
      if (head === null || head.next === null) return head;
      // 暂存一下原来的头next数据，作为一个新的头部数据
      let newHead = reverse(head.next);
      // 将原来的头部数据head，赋值给新的头部head.next数据的next
      head.next.next = head;
      // 将原来的头部的next数据设置为null
      head.next = null;
      return newHead;
    };
    this.head = reverse(this.head);
    return this.head;
  }
  reverseList2() {
    let oldHead = this.head;
    let newHead = null;
    // 使用while循环，将原来的链表每个元素依次放入到新的链表中，从而将位置互换
    while (oldHead != null) {
      // 暂存一下原来头数数据的next，以后作为下次的头部
      let tempHead = oldHead.next;
      // 给原来的头数据next设置为newHead,即表示移入到了新的链表
      oldHead.next = newHead;
      // 给原来的头数据放到新的链表中，作为头。
      newHead = oldHead;
      // 将原来链表的第二数据，即【暂存的头部】，赋值给旧的链表头
      oldHead = tempHead;
    }
    this.head = newHead;
    return this.head;
  }
  // 查看索引位置
  indexOf(target) {
    let index = 0;
    let current = this.head;
    while (current) {
      if (current.element === target) {
        return index;
      }
      index++;
      current = current.next;
    }
    return -1;
  }
  // 通过索引删除链表数据
  removeAt(index) {
    if (index < 0 || index > this.size) {
      throw new Error("index out of bounds");
    }
    let current = this.head;
    let prevNode = null;
    let i = 0;
    if (index === 0) {
      this.head = current.next;
    } else {
      while (i !== index) {
        i++;
        prevNode = current;
        current = current.next;
      }
      prevNode.next = current.next;
    }
    this.size--;
    return current.element;
  }
  // 通过链表的的值，删除链表中的元素，不存在的直接返回-1
  remove(target) {
    let index = this.indexOf(target);
    return this.removeAt(index);
  }
  // 判断链表是否为空
  isEmpty() {
    return this.size == 0;
  }
  // 获取链表的长度
  getSize() {
    return this.size;
  }
  // 获取链表的头部元素
  getHead(){
    return this.head.element;
  }
  // 将链表的数据转为字符串链式打印出来
  toString() {
    let str = '';
    let current = this.head;
    while (current){
      str+=current.element + (current.next ? "->" : "");
      current = current.next;
    }
    return str;
  }
}

let ll = new LinkedList();
ll.append(100);
ll.append(0, 200);
ll.append(1, 300);
ll.append(888);
console.dir(ll, { depth: 1000 });
ll.remove(100);
ll.reverseList2();
console.dir(ll, { depth: 1000 });
console.log(ll.toString());
